import tkinter as tk
from tkinter import ttk, messagebox
import threading
import time

class DFSVisualizer:
    def __init__(self, root):
        self.root = root
        self.root.title("深度优先搜索(DFS)可视化")
        self.root.geometry("800x700")
        
        # 默认网格大小
        self.rows = 10
        self.cols = 10
        
        # 状态定义
        self.EMPTY = 0      # 空白
        self.WALL = 1       # 墙壁
        self.START = 2      # 起点
        self.END = 3        # 终点
        self.VISITED = 4    # 已访问
        self.CURRENT = 5    # 当前节点
        self.PATH = 6       # 路径
        
        # 颜色映射
        self.colors = {
            self.EMPTY: "white",
            self.WALL: "black",
            self.START: "green",
            self.END: "red",
            self.VISITED: "lightblue",
            self.CURRENT: "yellow",
            self.PATH: "orange"
        }
        
        # 初始化网格
        self.grid = [[self.EMPTY for _ in range(self.cols)] for _ in range(self.rows)]
        self.start = (0, 0)
        self.end = (self.rows-1, self.cols-1)
        self.grid[self.start[0]][self.start[1]] = self.START
        self.grid[self.end[0]][self.end[1]] = self.END
        
        # 正在运行标志
        self.running = False
        self.animation_speed = 500  # 毫秒
        
        self.setup_ui()
        self.draw_grid()
    
    def setup_ui(self):
        # 控制面板
        control_frame = ttk.Frame(self.root)
        control_frame.pack(pady=10)
        
        # 按钮
        self.start_button = ttk.Button(control_frame, text="开始搜索", command=self.start_dfs)
        self.start_button.pack(side=tk.LEFT, padx=5)
        
        self.reset_button = ttk.Button(control_frame, text="重置网格", command=self.reset_grid)
        self.reset_button.pack(side=tk.LEFT, padx=5)
        
        self.clear_path_button = ttk.Button(control_frame, text="清除路径", command=self.clear_path)
        self.clear_path_button.pack(side=tk.LEFT, padx=5)
        
        # 速度控制
        ttk.Label(control_frame, text="速度:").pack(side=tk.LEFT, padx=(20, 5))
        self.speed_var = tk.StringVar(value="中等")
        speed_combo = ttk.Combobox(control_frame, textvariable=self.speed_var, 
                                  values=["慢速", "中等", "快速"], width=10, state="readonly")
        speed_combo.pack(side=tk.LEFT, padx=5)
        speed_combo.bind('<<ComboboxSelected>>', self.change_speed)
        
        # 网格大小控制
        ttk.Label(control_frame, text="行数:").pack(side=tk.LEFT, padx=(20, 5))
        self.row_var = tk.StringVar(value=str(self.rows))
        row_spin = ttk.Spinbox(control_frame, from_=5, to=20, width=5, 
                              textvariable=self.row_var, command=self.update_grid_size)
        row_spin.pack(side=tk.LEFT, padx=5)
        
        ttk.Label(control_frame, text="列数:").pack(side=tk.LEFT, padx=5)
        self.col_var = tk.StringVar(value=str(self.cols))
        col_spin = ttk.Spinbox(control_frame, from_=5, to=20, width=5,
                              textvariable=self.col_var, command=self.update_grid_size)
        col_spin.pack(side=tk.LEFT, padx=5)
        
        # 模式选择
        self.mode = tk.StringVar(value="wall")
        wall_radio = ttk.Radiobutton(control_frame, text="添加墙壁", variable=self.mode, value="wall")
        wall_radio.pack(side=tk.LEFT, padx=(20, 5))
        
        start_radio = ttk.Radiobutton(control_frame, text="设置起点", variable=self.mode, value="start")
        start_radio.pack(side=tk.LEFT, padx=5)
        
        end_radio = ttk.Radiobutton(control_frame, text="设置终点", variable=self.mode, value="end")
        end_radio.pack(side=tk.LEFT, padx=5)
        
        # 网格画布
        canvas_frame = ttk.Frame(self.root)
        canvas_frame.pack(expand=True, fill=tk.BOTH, padx=20, pady=10)
        
        self.canvas = tk.Canvas(canvas_frame, bg="white")
        self.canvas.pack(expand=True, fill=tk.BOTH)
        
        # 添加滚动条
        v_scrollbar = ttk.Scrollbar(canvas_frame, orient=tk.VERTICAL, command=self.canvas.yview)
        v_scrollbar.pack(side=tk.RIGHT, fill=tk.Y)
        h_scrollbar = ttk.Scrollbar(canvas_frame, orient=tk.HORIZONTAL, command=self.canvas.xview)
        h_scrollbar.pack(side=tk.BOTTOM, fill=tk.X)
        
        self.canvas.configure(yscrollcommand=v_scrollbar.set, xscrollcommand=h_scrollbar.set)
        
        # 绑定鼠标事件
        self.canvas.bind("<Button-1>", self.on_canvas_click)
        self.canvas.bind("<B1-Motion>", self.on_canvas_drag)
        
        # 状态标签
        self.status_label = ttk.Label(self.root, text="就绪")
        self.status_label.pack()
        
        # 图例
        legend_frame = ttk.Frame(self.root)
        legend_frame.pack(pady=10)
        
        legend_items = [
            (self.EMPTY, "空白"),
            (self.WALL, "墙壁"),
            (self.START, "起点"),
            (self.END, "终点"),
            (self.VISITED, "已访问"),
            (self.CURRENT, "当前"),
            (self.PATH, "路径")
        ]
        
        for color_type, text in legend_items:
            frame = ttk.Frame(legend_frame)
            frame.pack(side=tk.LEFT, padx=10)
            canvas = tk.Canvas(frame, width=20, height=20, bg=self.colors[color_type])
            canvas.pack(side=tk.LEFT)
            ttk.Label(frame, text=text).pack(side=tk.LEFT)
    
    def update_grid_size(self):
        try:
            new_rows = int(self.row_var.get())
            new_cols = int(self.col_var.get())
            
            if 5 <= new_rows <= 20 and 5 <= new_cols <= 20:
                self.rows = new_rows
                self.cols = new_cols
                
                # 保存旧的起点和终点位置
                old_start = self.start
                old_end = self.end
                
                # 创建新网格
                self.grid = [[self.EMPTY for _ in range(self.cols)] for _ in range(self.rows)]
                
                # 设置新的起点和终点
                self.start = (min(old_start[0], self.rows-1), min(old_start[1], self.cols-1))
                self.end = (min(old_end[0], self.rows-1), min(old_end[1], self.cols-1))
                
                self.grid[self.start[0]][self.start[1]] = self.START
                self.grid[self.end[0]][self.end[1]] = self.END
                
                self.draw_grid()
        except ValueError:
            pass
    
    def draw_grid(self):
        self.canvas.delete("all")
        
        # 计算单元格大小
        width = max(600, self.root.winfo_width() - 100)
        height = max(400, self.root.winfo_height() - 250)
        
        cell_width = width // self.cols
        cell_height = height // self.rows
        cell_size = min(cell_width, cell_height, 50)  # 最大50像素
        
        # 绘制网格
        for i in range(self.rows):
            for j in range(self.cols):
                x1 = j * cell_size
                y1 = i * cell_size
                x2 = x1 + cell_size
                y2 = y1 + cell_size
                
                color = self.colors[self.grid[i][j]]
                self.canvas.create_rectangle(x1, y1, x2, y2, fill=color, outline="gray")
        
        # 更新滚动区域
        self.canvas.configure(scrollregion=self.canvas.bbox("all"))
    
    def on_canvas_click(self, event):
        self.process_click(event)
    
    def on_canvas_drag(self, event):
        self.process_click(event)
    
    def process_click(self, event):
        # 获取画布坐标
        x = self.canvas.canvasx(event.x)
        y = self.canvas.canvasy(event.y)
        
        # 计算单元格大小
        width = max(600, self.root.winfo_width() - 100)
        height = max(400, self.root.winfo_height() - 250)
        cell_width = width // self.cols
        cell_height = height // self.rows
        cell_size = min(cell_width, cell_height, 50)
        
        # 计算点击的行列
        if cell_size > 0:
            col = int(x // cell_size)
            row = int(y // cell_size)
            
            if 0 <= row < self.rows and 0 <= col < self.cols:
                if self.mode.get() == "wall":
                    # 如果不是起点或终点，则设置为墙壁或空白
                    if (row, col) != self.start and (row, col) != self.end:
                        if self.grid[row][col] == self.WALL:
                            self.grid[row][col] = self.EMPTY
                        else:
                            self.grid[row][col] = self.WALL
                elif self.mode.get() == "start":
                    # 移动起点
                    if self.grid[row][col] != self.WALL and (row, col) != self.end:
                        self.grid[self.start[0]][self.start[1]] = self.EMPTY
                        self.start = (row, col)
                        self.grid[row][col] = self.START
                elif self.mode.get() == "end":
                    # 移动终点
                    if self.grid[row][col] != self.WALL and (row, col) != self.start:
                        self.grid[self.end[0]][self.end[1]] = self.EMPTY
                        self.end = (row, col)
                        self.grid[row][col] = self.END
                
                self.draw_grid()
    
    def change_speed(self, event=None):
        speed_map = {"慢速": 1000, "中等": 500, "快速": 100}
        self.animation_speed = speed_map[self.speed_var.get()]
    
    def reset_grid(self):
        self.grid = [[self.EMPTY for _ in range(self.cols)] for _ in range(self.rows)]
        self.start = (0, 0)
        self.end = (self.rows-1, self.cols-1)
        self.grid[self.start[0]][self.start[1]] = self.START
        self.grid[self.end[0]][self.end[1]] = self.END
        self.draw_grid()
        self.status_label.config(text="网格已重置")
    
    def clear_path(self):
        for i in range(self.rows):
            for j in range(self.cols):
                if self.grid[i][j] in [self.VISITED, self.CURRENT, self.PATH]:
                    self.grid[i][j] = self.EMPTY
        self.grid[self.start[0]][self.start[1]] = self.START
        self.grid[self.end[0]][self.end[1]] = self.END
        self.draw_grid()
        self.status_label.config(text="路径已清除")
    
    def get_neighbors(self, row, col):
        """获取相邻节点"""
        neighbors = []
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 右、下、左、上
        
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            if (0 <= new_row < self.rows and 
                0 <= new_col < self.cols and 
                self.grid[new_row][new_col] != self.WALL):
                neighbors.append((new_row, new_col))
        
        return neighbors
    
    def dfs_search(self):
        """执行深度优先搜索"""
        self.running = True
        visited = set()
        stack = [self.start]
        parent = {self.start: None}
        
        # 标记起点为已访问
        visited.add(self.start)
        
        while stack and self.running:
            current = stack.pop()
            
            # 如果找到终点
            if current == self.end:
                # 重构路径
                path = []
                node = current
                while node is not None:
                    path.append(node)
                    node = parent[node]
                
                # 在GUI上显示路径
                for node in reversed(path):
                    if node != self.start and node != self.end:
                        self.grid[node[0]][node[1]] = self.PATH
                        self.root.after(0, self.draw_grid)
                        time.sleep(self.animation_speed / 1000.0)
                
                self.status_label.config(text=f"找到路径! 长度: {len(path)}")
                self.running = False
                return True
            
            # 标记当前节点
            if current != self.start and current != self.end:
                self.grid[current[0]][current[1]] = self.CURRENT
                self.root.after(0, self.draw_grid)
                time.sleep(self.animation_speed / 1000.0)
            
            # 探索邻居节点
            for neighbor in self.get_neighbors(current[0], current[1]):
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append(neighbor)
                    parent[neighbor] = current
                    
                    # 标记为已访问
                    if neighbor != self.end:
                        self.grid[neighbor[0]][neighbor[1]] = self.VISITED
            
            # 更新当前节点为已访问（除非是起点或终点）
            if current != self.start and current != self.end:
                self.grid[current[0]][current[1]] = self.VISITED
            
            self.root.after(0, self.draw_grid)
            time.sleep(self.animation_speed / 1000.0)
        
        if self.running:
            self.status_label.config(text="未找到路径!")
        
        self.running = False
        return False
    
    def start_dfs(self):
        if self.running:
            return
        
        # 在新线程中运行DFS以避免阻塞GUI
        thread = threading.Thread(target=self.dfs_search)
        thread.daemon = True
        thread.start()
        self.status_label.config(text="正在搜索...")

def main():
    root = tk.Tk()
    app = DFSVisualizer(root)
    root.mainloop()

if __name__ == "__main__":
    main()